package main.leetcode.clockin.July;

/**
 * 410. 分割数组的最大值 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
 *
 * <p>注意: 数组长度 n 满足以下条件: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n)
 *
 * <p>示例: <br>
 * 输入: nums = [7,2,5,10,8] m = 2<br>
 * 输出: 18 <br>
 * 解释: 一共有四种方法将nums分割为2个子数组。 其中最好的方式是将其分为[7,2,5] 和 [10,8]， 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
 */
public class day25 {
    //    private long res = Integer.MAX_VALUE;

    public static void main(String[] args) {
        System.out.println(new day25().splitArray(new int[] {7, 2, 5, 10, 8}, 2));
        System.out.println(new day25().splitArray(new int[] {7, 2, 5, 10, 8}, 3));
        System.out.println(new day25().splitArray(new int[] {1, Integer.MAX_VALUE}, 2));
    }

    /** dp */
    //    public int splitArray(int[] nums, int m) {
    //        if (nums == null || nums.length < m) {
    //            throw new IllegalArgumentException("参数不满足要求。");
    //        }
    //        int n = nums.length;
    //
    //        int[] sum = new int[n + 1];
    //        sum[0] = nums[0];
    //        for (int i = 0; i < nums.length; ++i) {
    //            sum[i + 1] += sum[i] + nums[i];
    //        }
    //
    //        // dp[i][j]代表前i个数分成j段得到的最大连续子数组和中的最小值
    //        int[][] dp = new int[n + 1][m + 1];
    //        for (int[] ints : dp) {
    //            Arrays.fill(ints, Integer.MAX_VALUE);
    //        }
    //        dp[0][0] = 0;
    //
    //        // 前i个数
    //        for (int i = 1; i <= n; ++i) {
    //            int max = Math.min(i, m);
    //            // 分成j段
    //            for (int j = 1; j <= max; ++j) {
    //                // 分别以k为最后一个分割点
    //                for (int k = 0; k < i; ++k) {
    //                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], sum[i] - sum[k]));
    //                }
    //            }
    //        }
    //
    //        return dp[n][m];
    //    }

    /** dfs */
    //    public int splitArray(int[] nums, int m) {
    //        if (nums == null || nums.length < m) {
    //            throw new IllegalArgumentException("参数不满足要求。");
    //        }
    //        int[] sum = new int[nums.length + 1];
    //        sum[0] = nums[0];
    //        for (int i = 0; i < nums.length; ++i) {
    //            sum[i + 1] += sum[i] + nums[i];
    //        }
    //        dfs(nums, 0, m, 0, sum);
    //        return (int) res;
    //    }
    //
    //    private void dfs(int[] nums, int start, int m, int cur, int[] sum) {
    //        int n = nums.length - start;
    //        if (m == 1) {
    //            cur = Math.max(cur, sum[nums.length] - sum[start]);
    //            res = Math.min(res, cur);
    //            return;
    //        }
    //        for (int i = 1; i <= n - m + 1; ++i) {
    //            cur = Math.max(cur, sum[start + i] - sum[start]);
    //            dfs(nums, start + i, m - 1, cur, sum);
    //        }
    //    }

    /**
     * 贪心 + 二分
     *
     * <p>可以确定目标值必定为[max, sum]中的数，其中max为数组中的最大值，sum为数组元素总和，由此可以使用二分查找来确定最大和的最小值。
     */
    public int splitArray(int[] nums, int m) {
        if (nums == null || nums.length < m) {
            throw new IllegalArgumentException("参数不满足要求。");
        }
        int left = 0;
        int right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left >> 1);
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int[] nums, int mid, int m) {
        // 记录组数
        int cnt = 1;
        // 记录当前组的前缀和
        int pre = 0;
        // 遍历更新组数和前缀和
        for (int num : nums) {
            if (pre + num > mid) {
                ++cnt;
                pre = num;
            } else {
                pre += num;
            }
        }
        return cnt <= m;
    }
}
